﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Dwarf.Managed
{


    /// <summary>
    /// Solve the Graph traversal problem.
    /// </summary>
    /// <remarks> 
    ///For the demonstration purposes of the project,
    ///we have chosen Depth first search algorithm
    /// </remarks>
    class Solver
    {
        /// <summary>
        /// Instance of Graph.
        /// </summary>
        public Graph graph;

        public Solver()
        {

        }

        /// <summary>
        /// Based method.
        /// </summary>
        public void Solve()
        {
            Stack<int> s = new Stack<int>();
            //set the head of graph
            int headId = graph.getHeadId();
            graph.Visit(headId);
            s.Push(headId);
            //while stack not empty 
            while (s.Count != 0)
            {
                //take the first element
                int u = s.Peek();
                //for all edges of current vertex
                bool hasNoVisited = true;
                int[] edges = graph.GetNeighbouringVertices(u);
                for (int j = 0; j < edges.Length; j++)
                {
                    bool visited = graph.GetVisited(edges[j]) > 0;
                    if (!visited)
                    {
                        //adding new vertex to work stack
                        hasNoVisited = false;
                        s.Push(edges[j]);
                        graph.Visit(edges[j]);
                        break;
                    }
                }
                if (hasNoVisited)
                {
                    s.Pop();
                }

            }
        }
    }
}
